package com.cdream.basic.algorithm.leetcode.twoPointer;

import java.util.Random;

/**
 * @author cdream
 * @date 5/15/21
 */
public class Question215 {
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        new Question215().findKthLargest(new int[]{-1, -1}, 2);
    }

    /**
     * 快排+随机数
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {

        int start = 0;
        int end = nums.length - 1;
        int index = end - k + 1;
        return selectValue(nums, start, end, index);
    }

    private int selectValue(int[] nums, int start, int end, int index) {
        int q = randomPartition(nums, start, end);
        if (q == index) {
            return nums[q];
        } else {
            return q > index ? selectValue(nums, start, q - 1, index) : selectValue(nums, q + 1, end, index);
        }
    }

    private int randomPartition(int[] nums, int start, int end) {
        int r = new Random().nextInt(end - start + 1) + start;

        swap(nums, end, r);
        return partition(nums, start, end);
    }

    /**
     * 按照随机值将数组切分成两部分，[start,pivot-1][pivot+1,end]
     */
    private int partition(int[] nums, int start, int end) {
        // 比end小的都在左侧，比end大的都放在右侧
        int pivot = start - 1;
        for (int i = start; i < end; i++) {
            if (nums[i] <= nums[end]) {
                swap(nums, i, ++pivot);
            }
        }
        swap(nums, pivot + 1, end);
        return pivot + 1;
    }
}
